package Algorithm.floyd;

import java.util.Arrays;

//弗洛伊德算法，解决图中（所有顶点）到其他（所有顶点）的最短距离
public class FloydAlgorithm {
	public static void main(String[] args) {
		char[] vertex = {'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H'};
		//设置邻接矩阵,用 1000 表示两点距离很大，不连通
		final int N = 65535;
		int[][] matrix = {{0, 5, 7, N, N, N, 2, N},
				{5, 0, N, 9, N, N, 3, N},
				{7, N, 0, N, 8, N, N, N},
				{N, 9, N, 0, N, 4, N, 1},
				{N, N, 8, N, 0, 5, 4, N},
				{N, N, N, 4, 5, 0, 6, N},
				{2, 3, N, N, 4, 6, 0, N},
				{N, N, N, 1, N, N, N, N}};

		Graph graph = new Graph(vertex.length, matrix, vertex);
		graph.show();
		graph.floyd();
		graph.show();
		graph.getRoad(0, 3);

	}

}

class Graph {
	//存放顶点
	private char[] vertex;
	//保存图中（所有顶点）到其他（所有顶点）的距离，最后结果为最短距离
	private int[][] distance;
	//保存图中（所有顶点）到其他（所有顶点）的最短距离路径的前驱顶点
	private int[][] preVertex;

	/**
	 * @param length 顶点个数
	 * @param metrix 邻接矩阵
	 * @param vertex 顶点数组
	 */
	public Graph(int length, int[][] metrix, char[] vertex) {
		this.vertex = vertex;
		this.distance = metrix;
		this.preVertex = new int[length][length];
		//初始化前驱顶点数组，所有顶点都指向自己
		for (int i = 0; i < length; i++) {
			Arrays.fill(preVertex[i], i);
		}
	}

	public void show() {

		char[] vertex = {'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H'};
		System.out.println("====前驱顶点数组 preVertex ====");
		for (int i = 0; i < distance.length; i++) {
			System.out.print(vertex[i] + " : ");
			for (int j = 0; j < distance.length; j++) {
				System.out.print(preVertex[i][j] + " ");
			}
			System.out.println();
		}

		System.out.println("\n");

		System.out.println("====距离数组 distance ====");
		for (int i = 0; i < distance.length; i++) {
			System.out.print(vertex[i] + " : ");
			for (int j = 0; j < distance.length; j++) {
				System.out.printf("%c<%5d>, ", vertex[j], distance[i][j]);
			}
			System.out.println();
		}
		System.out.println("\n");
	}

	//==弗洛伊德算法=====================================
	public void floyd() {
		//保存距离
		int length = 0;
		//对中间顶点 的遍历，k为中间顶点下标
		for (int k = 0; k < distance.length; k++) {
			//对起点进行遍历
			for (int i = 0; i < distance.length; i++) {
				//对终点遍历
				for (int j = 0; j < distance.length; j++) {
					//求出 顶点i -> 顶点k + 顶点k -> 顶点j 的距离和
					length = distance[i][k] + distance[k][j];
					//如果（上面两段距离之和） 小于 顶点i -> 顶点j 直连的距离
					if (length < distance[i][j]) {
						//更新 距离表 中的距离
						distance[i][j] = length;

						//更新 前驱表
						preVertex[i][j] = preVertex[k][j];
					}
				}
			}
		}
	}

	//获取 start -> end 的最短路径
	public void getRoad1(int start, int end) {
		int index = end;
		if (index != start) {
			index = preVertex[start][index];
			getRoad1(start, index);
			System.out.print(vertex[index] + "->");
		}
	}

	public void getRoad(int start, int end) {
		getRoad1(start, end);
		System.out.print(vertex[end]);
		System.out.println("\n");
	}

	//==================================================
}
